//创建节点
class Node {
    constructor(element) {
        this.element = element;  //值
        this.left = null;        // 左侧子节点
        this.right = null;       //右侧子节点
    }
}
class Tree {
    constructor() {
        this.root = null; //根
    }
    //左侧子节点比父节点的值小
    //右侧子节点比父节点的值大
    //插入
    insert(element) {
        //创建节点
        let node = new Node(element);
        //判断书为空
        if (this.root === null) {
            this.root = node
        } else {
            this.insertNode(node, this.root)
        }
    }
    //插节点
    insertNode(newNode, rootNode) {
        //判断插入值和父级节点的大小
        if (newNode.element < rootNode.element) {
            //左侧
            if (rootNode.left === null) {
                rootNode.left = newNode;
            } else {
                this.insertNode(newNode, rootNode.left)
            }
        } else {
            //右侧
            if (rootNode.right === null) {
                rootNode.right = newNode;
            } else {
                this.insertNode(newNode, rootNode.right)
            }
        }
    }
    //最小值
    min() {
        return this.minNode(this.root);
    }
    minNode(rootNode) {
        while (rootNode.left != null) {
            rootNode = rootNode.left
        }
        return rootNode
    }
    //最大值
    max() {
        return this.maxNode(this.root);
    }
    maxNode(rootNode) {
        while (rootNode.right != null) {
            rootNode = rootNode.left
        }
        return rootNode
    }
    //找指定值搜索
    search(element) {
        return this.searchNode(element, this.root)
    }
    searchNode(element, rootNode) {
        //树为空
        if (rootNode === null) {
            return false
        }
        //不为空
        if (element < rootNode.element) {
            return this.searchNode(element, rootNode.left) // true
        }
        else if (element > rootNode.element) {
            return this.searchNode(element, rootNode.right) //false
        } else {
            return true
        }
    }
    //中序遍历
    inOrderTraverse(callback) {
        //this.root === 11
        this.inOrderTraverseNode(this.root, callback)
    }
    inOrderTraverseNode(node, callback) {
        if (node != null) {
            //11 7 5 3
            this.inOrderTraverseNode(node.left, callback);
            // 3
            callback(node.element)
            this.inOrderTraverseNode(node.right, callback);
        }
    }
    //前序
    preOrderTraverse(callback) {
        //this.root === 11
        this.preOrderTraverseNode(this.root, callback)
    }
    preOrderTraverseNode(node, callback) {
        if (node != null) {
            //11 7 5 3
            // 3
            callback(node.element)
            this.preOrderTraverseNode(node.left, callback);
            this.preOrderTraverseNode(node.right, callback);
        }
    }
    //后序
    nextOrderTraverse(callback) {
        //this.root === 11
        this.nextOrderTraverseNode(this.root, callback)
    }
    nextOrderTraverseNode(node, callback) {
        if (node != null) {
            //11 7 5 3
            // 3
            this.nextOrderTraverseNode(node.left, callback);
            this.nextOrderTraverseNode(node.right, callback);
            callback(node.element)

        }
    }
    //删除remove
    remove(element) {
        return this.removeNode(element, this.root)
    }
    removeNode(element, rootNode) {
        if (rootNode === null) {
            return null;
        }


        //大于
        if (element < rootNode.element) {
            //小于
            rootNode.left = this.removeNode(element, rootNode.left)
            return rootNode
        } else if (element > rootNode.element) {
            //大于
            rootNode.right = this.removeNode(element, rootNode.right)
            return rootNode
        } else {
            //相等
            //删除叶子节点  当子节点没有
            if (rootNode.left === null && rootNode.right === null) {
                rootNode = null;
                return rootNode;
            }
            //有一个子节点
            if (rootNode.left === null) {
                rootNode = rootNode.right
                return rootNode
            } else if (rootNode.right === null) {
                rootNode = rootNode.left;
                return rootNode
            }
            //删除有两个子节点
            //找最小子节点
            //此时 rootNode为20
            let endNode = this.minNode(rootNode.right)//endNode 25
            rootNode.element = endNode.element; //rootNode.element 为 25   endNode.element 25
            //25          rootNode.right => null
            rootNode.right = this.removeNode(endNode.element, rootNode.right)
            //endNode.element=== 25  rootNode.right=== null
            //rootNode.right === null
            //rootNode === 25
            return rootNode
        }
    }


}
let tree = new Tree()

tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(9)
tree.insert(3)
tree.insert(6)
tree.insert(8)
tree.insert(10)
tree.insert(15)
tree.insert(13)
tree.insert(12)
tree.insert(14)
tree.insert(20)
tree.insert(18)
tree.insert(25)
let arr = [];
let callback = (element) => {
    console.log(element)
    arr.push(element)
}
tree.remove(6)
tree.remove(5)
tree.remove(20)
console.log(tree)
// tree.inOrderTraverse(callback)
tree.preOrderTraverse(callback)

// console.log(arr,'arr')
//冒泡排序
function fun(arr = []) {
    let { length } = arr;
    for (let i = 1; i < length; i++) {
        for (j = 0; j < length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
            }
        }
    }
    console.log(arr, '冒泡')
}
fun(arr);
//选择
function trr(arr=[]) {
    let {length} = arr
    let min ;
    for(let i = 0 ; i < length-1 ; i++){
        min = i;
        for(let j = i+1 ; j < length  ; j++){
            if(arr[min] < arr[j]){
                min = j
            }
        }
        if(min != i){
            [arr[i],arr[min]] = [arr[min],arr[i]]
        }
    }
    console.log(arr,'选择')
}
trr(arr)
tree.nextOrderTraverse(callback);

